PhD

related work.tex (40403B)

---

 \section{Related Work}
 \label{sec:graph:related work}
 In the previous section, we show that the attributed multigraph encoding we introduced in Section~\ref{sec:graph:encoding} can help us leverage additional information for the relation extraction task.
 In this section, we present the existing framework for computing distributed representations of graphs.
 In most cases, these process simple undirected graphs \(G=(V, E)\).
 Still, these methods are applicable to our relation extraction multigraph with some modifications, as shown in Sections~\ref{sec:graph:r-gcn} and~\ref{sec:graph:approach}.
 
 The use of graphs in deep learning has seen a recent surge of interest over the last few years.
 This produced a set of models known as graph neural networks (\textsc{gnn}) and graph convolutional networks (\textsc{gcn}).%
 \sidenote{
 	The term \textsc{gcn} is used with different meanings by various authors.
 	\textsc{gcn}s are always \textsc{gnn}s, but the reverse is not true.
 	However, in practice, the \textsc{gnn}s we describe in this section can essentially be described as \textsc{gcn}s.
 	We use the term \textsc{gcn} to describe models whose purpose is to have a similar function on graphs as \textsc{cnn}s have on images.
 	Some authors only refer to the model of \textcite{gcn_spectral_semi} described in Section~\ref{sec:graph:spectral gcn} as a \textsc{gcn}.
 	In this case, what we call \textsc{gcn} can be called conv\textsc{gnn} (convolutional graph neural networks).
 	In any case, \textsc{gnn} and \textsc{gcn} can be considered almost synonymous for the purpose of this thesis since we don't describe any exotic \textsc{gnn} which clearly falls outside of the realm of \textsc{gcn}.
 	\label{note:graph:gcn vs gnn}
 }
 While the first works on \textsc{gnn} started more than twenty years ago \parencite{gnn_early}, we won't go into a detailed historical review, and we exclusively focus on recent models.
 Note that we already presented an older graph-based approach in Section~\ref{sec:relation extraction:label propagation}, the label propagation algorithm.
 We also discussed \textsc{epgnn} in Section~\ref{sec:relation extraction:epgnn}, which is a model built on top of a \textsc{gcn}.
 We further draw parallels between \textsc{epgnn} and our proposed approach in Section~\ref{sec:graph:topological features}.
 
 The thread of reasoning behind this section is as follows:
 \begin{itemize}[nosep]
 	\item We present the ``usual'' way to process graphs (Sections~\ref{sec:graph:random walk}--\ref{sec:graph:r-gcn}).
 	\item We present the theory behind these methods (Section~\ref{sec:graph:weisfeiler-leman}).
 	\item We show how this theoretical background can help us design a new approach specific to the unsupervised relation extraction task (Section~\ref{sec:graph:approach}).
 \end{itemize}
 In this related work overview, we mainly describe algorithms working on standard \(G=(V, E)\) graphs, not the labeled multigraphs of Section~\ref{sec:graph:encoding}, with the exception of Section~\ref{sec:graph:r-gcn}.
 We start by quickly describing models based on random walks in Section~\ref{sec:graph:random walk}; these are spatial methods which serve as a gentle introduction to the manipulation of graphs by neural networks.
 Furthermore, they were influential in the development of subsequent models and in our preliminary analysis with computation of path statistics (Section~\ref{sec:graph:analysis}), which allows us to draw parallels with more modern approaches.
 We then introduce the two main classes of \textsc{gcn}---which consequently are also the two main classes of \textsc{gnn}---used nowadays: spectral (Section~\ref{sec:graph:spectral gcn}) and spatial (Section~\ref{sec:graph:spatial gcn}).
 Apart from the few works mentioned in Chapter~\ref{chap:relation extraction}, \textsc{gnn}s were seldom used for relation extraction.
 We, therefore, focus on the evaluation of \textsc{gnn} on an entity classification task, which while different from our problem, works on similar data.
 In Section~\ref{sec:graph:r-gcn}, we describe models designed to handle relational data in a knowledge base, in particular \textsc{r-gcn}.
 We close this related work with a presentation of the Weisfeiler--Leman isomorphism test in Section~\ref{sec:graph:weisfeiler-leman}; it serves as a theoretical motivation behind both \textsc{gcn}s and our proposed approach.
 
 \subsection{Random-Walk-Based Models}
 \label{sec:graph:random walk}
 DeepWalk \parencitex{deepwalk} is a method to learn vertex representations from the structure of the graph alone.
 The representations encode how likely it is for two vertices to be close to each other in the graph.
 To this end, DeepWalk models the likelihood of random walks in the graph (Section~\ref{sec:graph:analysis}).
 These walks are simply sequences of vertices.
 To obtain a distributed representation out of them, we can use the \textsc{nlp} approaches of Sections~\ref{sec:context:word} and~\ref{sec:context:sentence} by treating the set of vertices as the vocabulary \(V=\entitySet\).
 In particular, DeepWalk uses the skip-gram model of Word2vec (Section~\ref{sec:context:skip-gram}), using hierarchical softmax to approximate the partition function over all words---i.e.~vertices.
 Vertices part of the same random walk are used as positive examples.
 In the same way that learning representations to predict the neighborhood of a word gives good word representations, modeling the neighborhood of a vertex gives good vertex representations.
 
 \Textcite{deepwalk} evaluate their model on a node classification task.
 For example, one of the datasets they use is BlogCatalog \parencite{blogcatalog}, where vertices correspond to blogs, edges are built from social network connections between the various bloggers, and predicted labels are the set of topics on which each blog focuses.
 DeepWalk is a transductive method but was extended into an inductive approach called planetoid \parencitex{planetoid}.
 Planetoid also proposes an evaluation on an entity classification task performed on the \textsc{nell} dataset.
 The goal of this task is to find the type of an entity (e.g.~person, organization, location\dots) in a knowledge base (Section~\ref{sec:context:knowledge base}).
 To this end, a special bipartite%
 \sidenote{
 	A bipartite graph is a graph \(G=(V, E)\) where the vertices can be split into two disjoint sets \(V_1\cup V_2=V\) such that all edges \(e\in E\) have one endpoint in \(V_1\) and one endpoint in \(V_2\).
 }
 graph \(G_\textsc{b} = (V_\textsc{b}, E_\textsc{b})\) is constructed where \(V_\textsc{b}=\entitySet\cup\relationSet\) and:
 \begin{equation*}
 	E_\textsc{b} = \big\{\, \{e, r\}\subseteq V_\textsc{b} \mathrel{\big|} \exists e'\in\entitySet : (e, r, e') \in\kbSet\lor (e', r, e)\in\kbSet \,\big\}
 \end{equation*}
 This clearly assumes \hypothesis{biclique}: for each relation the information of ``which \(e_1\)'' corresponds to ``which \(e_2\)'' is discarded.
 However this information is not as crucial for entity classification as it is for relation extraction.
 A small example of graph \(G_\textsc{b}\) obtained this way is given in Figure~\ref{fig:graph:nell bipartite}.
 The model is trained by jointly optimizing the negative sampling loss and the the log-likelihood of labeled examples.
 On unseen entities, planetoid reach an accuracy of 61.9\% when only 0.1\% of entities are labeled.
 
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/graph/nell bipartite.tex}
 	\scaption[\textsc{nell} dataset bipartite graph.]{
 		\textsc{nell} dataset bipartite graph.
 		Entities are on the left, while relation slots are on the right.
 		In this graph, the edges are left unlabeled.
 		\label{fig:graph:nell bipartite}
 	}
 \end{marginfigure}
 
 Using random walks allows DeepWalk and planetoid to leverage the pre-existing \textsc{nlp} literature.
 However, for each sample, only a small fraction of the neighborhood---two neighbors at most---of each node is considered to make a prediction.
 Subsequent methods focused on modeling the information of the whole neighborhood jointly.
 
 \subsection{Spectral \textsc{gcn}}
 \label{sec:graph:spectral gcn}
 The first approaches to successfully model the neighborhood of vertices jointly were based on spectral graph theory \parencite{gcn_spectral_early}.
 In practice, this means that the graph is manipulated through its Laplacian matrix instead of directly through the adjacency matrix.
 In this section, we base our presentation of spectral methods on the work of \textcitex{gcn_spectral_semi}[-11mm].
 
 \begin{marginparagraph}[-3mm]
 	The graph Laplacian is similar to the standard Laplacian measuring the divergence of the gradient (\(\laplace = \nabla^2\)) of scalar functions.
 	Except that the graph gradient is an operator mapping a function on vertices to a function on edges:
 	\begin{equation*}
 		(\nabla \vctr{f})_{ij} = f_i - f_j
 	\end{equation*}
 	And that the graph divergence is an operator mapping a function on edges to a function on vertices:
 	\begin{equation*}
 		(\operatorname{div} \mtrx{G})_i = \sum_{j\in V} m_{ij} g_{ij}
 	\end{equation*}
 	Given these definitions, the graph Laplacian is defined as \(\laplace = - \operatorname{div} \nabla\).
 	Applying \(\laplace\) to a signal \(\vctr{x}\in\symbb{R}^n\) is equivalent to multiplying this signal by \(\laplacian{c}\) as defined in Equation~\ref{eq:graph:laplacian}: \(\laplace \vctr{x} = \laplacian{c} \vctr{x}\).
 \end{marginparagraph}
 
 We start by introducing some basic concepts from spectral graph theory used to define the convolution operator on graphs.
 The Laplacian of an undirected graph \(G=(V, E)\) can be defined as:
 \begin{equation}
 	\laplacian{c} = \mtrx{D} - \mtrx{M},
 	\label{eq:graph:laplacian}
 \end{equation}
 where \(\mtrx{D}\in\symbb{R}^{n\times n}\) is the diagonal matrix of vertex degrees \(d_{ii} = \gfdegree(v_i)\) and \(\mtrx{M}\in\symbb{R}^{n\times n}\) is the adjacency matrix.
 Equation~\ref{eq:graph:laplacian} defines the combinatorial Laplacian; however, spectral \textsc{gcn}s are usually defined on the normalized symmetric Laplacian:
 \begin{equation*}
 	\laplacian{sym} = \mtrx{D}^{-1\fracslash 2} \laplacian{c} \mtrx{D}^{-1\fracslash 2} = \mtrx{I} - \mtrx{D}^{-1\fracslash 2} \mtrx{M} \mtrx{D}^{-1\fracslash 2}.
 \end{equation*}
 
 Using this definition, we can then take the eigendecomposition of the Laplacian \(\laplacian{sym}=\mtrx{U}\mtrx{\Lambda}\mtrx{U}^{-1}\), where \(\mtrx{\Lambda}\) is the ordered spectrum---the diagonal matrix of eigenvalues sorted in increasing order---and \(\mtrx{U}\) is the matrix of normalized eigenvectors.
 For an undirected graph, the matrix \(\mtrx{M}\) is symmetric, therefore \(\mtrx{U}\) is orthogonal.
 The orthonormal space formed by the normalized eigenvectors is the Fourier space of the graph.
 In other words, we can define the graph Fourier transform of a signal \(\vctr{x}\in\symbb{R}^V\) as:
 \begin{marginparagraph}[-1cm]
 	The expansion of signals in terms of eigenfunctions of the Laplace operator is the leading parallel between the graph Fourier transform and the classical Fourier transform on \(\symbb{R}\) \parencite{graph_fourier}.
 	In \(\symbb{R}\), the eigenfunctions \(\xi\mapsto e^{2\pi i\xi x}\) correspond to low frequencies when \(x\) is small.
 	In the same way, the eigenvectors of the graph Laplacian associated with small eigenvalues assign similar values to neighboring vertices.
 	In particular the eigenvector associated with the eigenvalue 0 is constant with value \(1\divslash\sqrt{n}\).
 	On the other hand, eigenvectors associated with large eigenvalues correspond to high frequencies and encode larger changes of value between neighboring vertices.
 \end{marginparagraph}
 \begin{equation*}
 	\gffourier(\vctr{x}) = \mtrx{U}\transpose \vctr{x}.
 \end{equation*}
 Furthermore since the induced space is orthogonal, the inverse Fourier transform is simply defined as:
 \begin{equation*}
 	\gfinvfourier(\vctr{x}) = \mtrx{U} \vctr{x}.
 \end{equation*}
 Having defined the Fourier transform on graphs, we can use the definition of convolutions as multiplications in the Fourier domain to define convolution on graphs:
 \begin{equation}
 	\vctr{x} * \vctr{w} = \gfinvfourier(\gffourier(\vctr{x}) \odot \gffourier(\vctr{w})),
 	\label{eq:graph:convolution}
 \end{equation}
 where \(\odot\) denotes the Hadamard (element-wise) product.
 Note that the convolution operator implicitly depends on the graph \(G\) since \(\mtrx{U}\) is defined from the adjacency matrix \(\mtrx{M}\).
 The signal \(\vctr{w}\) in Equation~\ref{eq:graph:convolution} has the same function as the parametrized filter of \textsc{cnn} (Equation~\ref{eq:context:convolution}).
 Instead of learning \(\vctr{w}\) in the spatial domain, we can directly parametrize its Fourier transform \(\vctr{w}_\vctr{\theta} = \diagonal(\gffourier(\vctr{w}))\), %
 \begin{marginparagraph}
 	\(\diagonal(\vctr{x})\) is the diagonal matrix with values of the vector \(\vctr{x}\) along its diagonal.
 \end{marginparagraph}
 simplifying Equation~\ref{eq:graph:convolution} into:
 \begin{equation}
 	% ( ͡° ͜ʖ ͡°) UwU
 	\vctr{x} * \vctr{w}_\vctr{\theta} = \mtrx{U} \vctr{w}_\vctr{\theta} \mtrx{U}\transpose \vctr{x}.
 	\label{eq:graph:filter convolution}
 \end{equation}
 While \(\vctr{w}_\vctr{\theta}\) could be learned directly \parencite{gcn_spectral_early}, \textcite{chebnet} propose to approximate it by Chebyshev polynomials of the first kind (\(T_k\)) of the spectrum \(\mtrx{\Lambda}\):
 \begin{equation}
 	\vctr{w}_\vctr{\theta}(\mtrx{\Lambda}) = \sum_{k=0}^{K} \theta_k T_k(\mtrx{\Lambda}).
 	\label{eq:graph:filter decomposition}
 \end{equation}
 The rationale is that computing the eigendecomposition of the graph Laplacian is too computationally expensive.
 The Chebyshev polynomials approximation is used to localize the filter; since the \(k\)-th Chebyshev polynomial is of degree \(k\), only values of vertices at a distance of at most \(k\) are needed.%
 \sidenote[][-39mm]{
 	The reasoning behind this localization is the same as the one underlying the fact that the \(k\)-th power of the adjacency matrix gives the number of walks of length \(k\) (Section~\ref{sec:graph:analysis}).
 }
 This is similar to how \textsc{cnn}s are usually computed; simple very localized filters are used instead of taking the Fourier transform of the whole input matrix to compute convolution with arbitrarily complex functions.
 Chebyshev polynomials of the first kind are defined as:
 \begin{marginparagraph}[-32mm]
 	Despite its appearance, Equation~\ref{eq:graph:chebyshev cos} defines a series of polynomials which can be obtained through the application of various trigonometric identities.
 	An alternative but equivalent definition is through the following recursion:
 	\begin{align*}
 		T_0(x) & = 1 \\
 		T_1(x) & = x \\
 		T_{k+1}(x) & = 2x T_k(x) - T_{k-1}(x)
 	\end{align*}
 	The plot of the first five Chebyshev polynomials of the first kind follows:
 	\input{mainmatter/graph/chebyshev.tex}
 \end{marginparagraph}
 \begin{equation}
 	T_k(\cos x) = \cos(k x).
 	\label{eq:graph:chebyshev cos}
 \end{equation}
 They form a sequence of orthogonal polynomials on the interval \([-1, 1]\) with respect to the weight \(1\divslash\sqrt{1-x^2}\), meaning that for \(k\neq k'\):
 \begin{equation*}
 	\int_{-1}^1 T_k(x) T_{k'}(x) \frac{\diff x}{\sqrt{1-x^2}} = 0.
 \end{equation*}
 
 The filter defined by Equation~\ref{eq:graph:filter decomposition} is \(K\)-localized, meaning that the value of the output signal on a vertex \(v\) is computed from the value of \(\vctr{x}\) on vertices at distance at most \(K\) of \(v\).
 This can be seen by plugging Equation~\ref{eq:graph:filter decomposition} back into Equation~\ref{eq:graph:filter convolution}, noticing that it depends on the \(k\)-th power of the Laplacian and thus of the adjacency matrix.%
 \sidenotemark% XXX No more space for sidenote on this page
 
 \leavevmode
 \sidenotetext{% XXX No more space for sidenote on previous page
 	Derivation of the dependency on \(\laplacian{sym}^k\) for the proof of \(K\)-locality:
 	\begin{align*}
 		\vctr{x} * \vctr{w}_\vctr{\theta}(\mtrx{\Lambda})
 			& = \mtrx{U} \left( \sum_{k=0}^{K} \theta_k T_k(\mtrx{\Lambda}) \right) \mtrx{U}\transpose \vctr{x} \\
 			& = \left( \sum_{k=0}^{K} \theta_k \mtrx{U} T_k(\mtrx{\Lambda}) \mtrx{U}\transpose \right) \vctr{x} \\
 			& = \left( \sum_{k=0}^{K} \theta_k T_k(\laplacian{sym}) \right) \vctr{x}
 	\end{align*}
 	For the last equality, notice that \(\laplacian{sym}^k = (\mtrx{U}\mtrx{\Lambda}\mtrx{U}\transpose)^k = \mtrx{U}\mtrx{\Lambda}^k\mtrx{U}\transpose\) since \(\mtrx{U}\) is orthogonal.
 	This can also be applied to the (diagonal) constant term.
 }%
 \Textcite{gcn_spectral_semi} proposed to use \(K=1\) with several further optimizations we won't delve into.
 Using \(K=1\) means that their method computes the activation of a node only from its activation and the activations of its neighbors at the previous layer.
 This makes the \textsc{gcn} of \textcite{gcn_spectral_semi} quite similar to spatial methods described in Section~\ref{sec:graph:spatial gcn}.
 All the equations given thus far were for a single scalar signal; however, we usually work with vector representations for all nodes, \(\mtrx{X}\in\symbb{R}^{n\times d}\).
 In this case, the layer \(\ell\) of a \textsc{gcn} can be described as:
 \begin{equation*}
 	\mtrx{H}^{(\ell+1)} = \ReLU\left((\mtrx{D}+\mtrx{I})^{-1\fracslash2} (\mtrx{M}+\mtrx{I}) (\mtrx{D}+\mtrx{I})^{-1\fracslash2} \mtrx{H}^{(\ell)} \mtrx{\Theta}^{(\ell)}\right)
 \end{equation*}
 Where \(\mtrx{\Theta}\in\symbb{R}^{d\times d}\) is the parameter matrix.
 Using \(\mtrx{H}^{(0)} = \mtrx{X}\), we can use a \textsc{gcn} with \(L\) layers to combine the embeddings in the \(L\)-localized neighborhood of each vertex into a contextualized representation.
 
 \Textcite{gcn_spectral_semi} evaluate their model on the same \textsc{nell} dataset used by planetoid with the same 0.1\% labeling rate.
 They train their model by maximizing the log-likelihood of labeled examples.
 They obtain an accuracy of 66.0\%, which is an increase of 4.9 points over planetoid.
 
 \subsection{Spatial \textsc{gcn}}
 \label{sec:graph:spatial gcn}
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/graph/graph convolution parallel.tex}
 	\scaption[Parallel between two-dimensional \textsc{cnn} data and \textsc{gcn} data.]{
 		Parallel between two-dimensional \textsc{cnn} data and \textsc{gcn} data.
 		\label{fig:graph:graph convolution parallel}
 	}
 \end{marginfigure}
 \sidecite{graphsage}% XXX Insert the citation between the figure and the 1-dim CNN sidenote
 
 Spatial methods directly draw from the comparison with \textsc{cnn} in the spatial domain.
 As shown by Figure~\ref{fig:graph:graph convolution parallel}, the lattice on which a 2-dimensional%
 \sidenote{
 	Even though the same comparison could be made with 1-dimensional \textsc{cnn} as introduced in Section~\ref{sec:context:cnn}, the similarity is less visually striking.
 	Especially when considering a filter of width 3, in which case the equivalent graph is a simple path graph: \input{mainmatter/graph/path graph.tex}\kern-1mm.
 }
 \textsc{cnn} is applied can be seen as a graph with a highly regular connectivity pattern.
 In this section, we introduce spatial \textsc{gcn} by following the Graph\textsc{sage} model \parencite{graphsage}.
 
 When computing the activation of a specific node with a \textsc{cnn}, the filter is centered on this node, and each neighbor is multiplied with a corresponding filter element.
 The products are then aggregated by summation.
 Spatial \textsc{gcn}s purpose to mimic this process.
 The main obstacle to generalizing this spatial view of convolutions to graphs is the irregularity of neighborhoods.%
 \sidenote{
 	Interestingly enough, this is also a problem with standard \textsc{cnn}s when dealing with values at the edges of the matrix.
 }
 In a graph, nodes have different numbers of neighbors; a fixed-size filter cannot be used.
 Graph\textsc{sage} proposes several aggregators to replace this product--sum process:
 \begin{description}
 	\item[Mean aggregator] The neighbors are averaged and then multiplied by a single filter \(\mtrx{W}^{(l)}\):
 		\begin{equation*}
 			\operatorname{aggregate}_\text{mean}^{(\ell+1)}(v) = \sigmoid\left(\mtrx{W}^{(\ell)} \frac{1}{\gfdegree(v)+1} \sum_{u\in\gfneighbors(v)\cup\{v\}} \hspace{-3mm} \vctr{h}_u^{(\ell)}\right).
 		\end{equation*}
 		A spatial \textsc{gcn} using this aggregator is close to the \textsc{gcn} of \textcite{gcn_spectral_semi} with \(K=1\) presented in Section~\ref{sec:graph:spectral gcn}.
 	\item[L\textmd{\textsc{stm}} aggregator]
 		An \textsc{lstm} (Section~\ref{sec:context:lstm}) is run through all neighbors with the final hidden state used as the output of the layer.
 		\begin{equation*}
 			\operatorname{aggregate}_\textsc{lstm}^{(\ell+1)}(v) = \operatorname{\textsc{lstm}}^{(\ell)}\left(\left(\vctr{h}_u^{(\ell)}\right)_{u\in \gfneighbors(v)}\right)_{\gfdegree(v)}.
 		\end{equation*}
 		Since \textsc{lstm}s are not permutation-invariant, the order in which the neighbors are presented is important.
 	\item[Pooling aggregator]
 		A linear layer is applied to all neighbors which are then pooled through a \(\max\) operation.
 		\begin{equation*}
 			\operatorname{aggregate}_\text{max}^{(\ell+1)}(v) = \max\left(\left\{\,\mtrx{W}^{(\ell)}\vctr{h}_u^{(\ell)} + \vctr{b}^{(\ell)} \middlerel{|} u\in\gfneighbors(v)\,\right\}\right).
 		\end{equation*}
 		Note that the maximum is applied feature-wise.
 \end{description}
 Using one of these aggregator, a Graph\textsc{sage} layer performs the three following operations for all vertices \(v\in V\):
 \begin{marginparagraph}
 	As usual the matrices \(\mtrx{W}^{(l)}_i\) are trainable model parameters.
 \end{marginparagraph}
 \begin{align*}
 	\vctr{a}_v^{(\ell+1)} & \gets \operatorname{aggregate}^{(\ell+1)}(v) \\
 	\vctr{h}_v^{(\ell+1)} & \gets \sigmoid\left(\mtrx{W}_1^{(\ell)} \vctr{h}_v^{(\ell)} + \mtrx{W}_2^{(\ell)} \vctr{a}_v^{(\ell+1)}\right) \\
 	\vctr{h}_v^{(\ell+1)} & \gets \vctr{h}_v^{(\ell+1)} \divslash \big\|\vctr{h}_v^{(\ell+1)}\big\|_2 .
 \end{align*}
 However, this approach still performs poorly when the graph is irregular.%
 \sidenote{
 	In graph theory, a \(k\)-regular graph is a graph where all vertices have degree \(k\).
 	By irregular, we mean that the distribution of vertices degrees has high variance; we don't use the term in its formal ``highly irregular'' meaning.
 	This is indeed the case in scale-free graphs, as their variance is infinite when \(\gamma<3\).
 }
 In particular, high-degree vertices---such as ``United States'' in \textsc{t-re}x as described in Section~\ref{sec:graph:analysis}---incur significant memory usage.
 To solve this, Graph\textsc{sage} proposes to sample a fixed-size neighborhood for each vertex during training.
 Their representation is therefore computed from a small number of neighbors.
 Since \(L\) layers of Graph\textsc{sage} produce \(L\)-localized representations, vertices need to be sampled at most at distance \(L\) of the vertex for which we want to generate a representation.
 \Textcite{graphsage} propose an unsupervised negative sampling loss to train their \textsc{gcn} such that adjacent vertices have similar representations:
 \begin{equation}
 	\loss{gs} = \sum_{(u, v)\in E}
 	\log \sigmoid\left(\vctr{z}_v\transpose \vctr{z}_u\right)
 	- \gamma \expectation_{v'\sim\uniformDistribution(V)}
 		\left[ \log \sigmoid\left(-\vctr{z}_{v'}\transpose \vctr{z}_u\right) \right]
 	\label{eq:graph:graphsage loss}
 \end{equation}
 where \(\mtrx{Z} = \mtrx{H}^{(L)}\) is the activation of the last layer and \(\gamma\) is the number of negative samples.
 
 One of the advantages of Graph\textsc{sage} compared to the approach of \textcite{gcn_spectral_semi} is that it is inductive, whereas the spectral \textsc{gcn} presented in Section~\ref{sec:graph:spectral gcn} is transductive.
 Indeed, in the spectral approach, the filter is trained for a specific eigenvectors matrix \(\mtrx{U}\) which depends on the graph.
 If the graph changes, everything must be re-trained from scratch.
 In comparison, the parameters learned by Graph\textsc{sage} can be reused for a different graph without any problem.
 
 A limitation of Graph\textsc{sage} is that the contribution of each neighbor to the representation of a vertex \(v\) is either fixed at \(1\divslash (\gfdegree(v)+1)\) (with the mean aggregator) or not modeled explicitly.
 The same can be observed with the model of \textcite{gcn_spectral_semi}, where the representation of each neighbor \(u\) is nonparametrically weighted by \(1\divslash\sqrt{\gfdegree(v)+\gfdegree(u)}\).
 
 In contrast, graph attention network (\textsc{gat}, \citex{graph_attention_network}) proposes to parametrize this weight with a model similar to the attention mechanism presented in Section~\ref{sec:context:attention}.
 The output is built using an attention-like%
 \sidenote{
 	\Textcite{graph_attention_network} actually propose to use multi-head attention (Section~\ref{sec:context:transformer attention}).
 	We describe their model with a single attention head for ease of notation.
 }
 convex combination of transformed neighbors' representations:
 \begin{equation*}
 	\vctr{h}^{(\ell+1)}_v \gets \sigmoid\left(\sum_{u\in\gfneighbors(v)\cup\{v\}} \hspace{-3mm} \alpha^{(\ell)}_{vu} \mtrx{W}^{(\ell)} \vctr{h}_u^{(\ell)}\right),
 \end{equation*}
 where \(\alpha^{(\ell)}_{vu}\), the attention given by \(v\) to neighbor \(u\) at layer \(\ell\), is computed using a softmax:
 \begin{marginparagraph}
 	LeakyReLU \parencite{leakyrelu} is a variant of ReLU where the negative domain is linear with a small slope instead of being mapped to zero:
 	\begin{equation*}
 		\operatorname{LeakyReLU}(x) =
 		\begin{cases}
 			x & \text{if } x>0, \\
 			0.01x & \text{otherwise}. \\
 		\end{cases}
 	\end{equation*}
 \end{marginparagraph}
 \begin{equation*}
 	\alpha^{(\ell)}_{vu} \propto \exp \operatorname{LeakyReLU}\left(\vctr{g}^{(\ell)\transposesym}
 	\begin{bmatrix}
 		\mtrx{W}^{(\ell)}_\textsc{gat} \vctr{h}_v \\
 		\mtrx{W}^{(\ell)}_\textsc{gat} \vctr{h}_u
 	\end{bmatrix} \right).
 \end{equation*}
 As usual, the matrices \(\mtrx{W}\) are parameters, as well as the vector \(\vctr{g}\) which is used to combine the representations of the two vertices into a scalar weight.
 
 While \textsc{gat} and Graph\textsc{sage} can be trained in an unsupervised fashion following Equation~\ref{eq:graph:graphsage loss}, they can also be used as building blocks for larger models, similarly to how we use \textsc{cnn} in Chapter~\ref{chap:fitb}.
 Coupled with the fact that they have a simpler theoretical background and are easier to implement, spatial methods have become ubiquitous to graph-based approaches in the last few years.
 
 \subsection{\textsc{gcn} on Relation Graphs}
 \label{sec:graph:r-gcn}
 All the work introduced in the above sections is about simple undirected graphs \(G=(V, E)\).
 In contrast, in Section~\ref{sec:graph:encoding}, we encoded the relation extraction problem on attributed multigraphs \(G=(\entitySet, \arcSet, \gfendpoints, \gfrelation)\).
 Some works propose to extend \textsc{gcn} to the case of multigraphs, especially when dealing with knowledge bases.%
 \sidenote{
 	In this case, the multigraph is simply labeled since the set of relations is finite.
 	In contrast, in the relation extraction problem, the multigraph is attributed.
 	The arcs are associated with a sentence from an infinite set of possible sentences.
 }
 This is the case of \textsc{r-gcn} \parencitex{rgcn}, a graph convolutional network for relational data.
 The input graph is not labeled with sentences (\(\gfsentence\)) since \textsc{r-gcn} intents to model a knowledge base \(\kbSet\).
 This means that while \(G\) is a multigraph, the subgraphs \(G_\gfsr\) are simple graphs for all relations \(r\in\relationSet\).
 \textsc{r-gcn}s exploit this by using a separate \textsc{gcn} filter for each relation.
 An \textsc{r-gcn} layer can be defined as:
 \begin{marginparagraph}
 	Note that only the outgoing neighbors \(\gfneighborsrr\) are taken since for each incoming neighbor labeled \(r\), there is an outgoing one labeled \(\breve{r}\).
 \end{marginparagraph}
 \begin{equation}
 	\vctr{h}^{(\ell+1)}_v \gets \sigmoid\left(\mtrx{W}_0^{(\ell)} \vctr{h}_v^{(\ell)} + \sum_{r\in\relationSet}\sum_{u\in\gfneighborsrr(v)} \mtrx{W}_r^{(\ell)} \vctr{h}_u^{(\ell)} \right),
 	\label{eq:graph:r-gcn layer}
 \end{equation}
 \begin{marginparagraph}
 	Paralleling the notations used for \textsc{cnn}s in Section~\ref{sec:context:cnn}, we use \(d\) to denote the dimension of embeddings at layer \(\ell\) and \(d'\) for the dimension at layer \(\ell+1\).
 	More often than not, the same dimension is used at all layers \(d'=d\).
 	In the following, we use \(d\) as a generic notation for embedding and latent dimensions.
 \end{marginparagraph}
 where \(\mtrx{W}_0\in\symbb{R}^{d'\times d}\) is used for the (implicit) self-loop, while \(|\relationSet|\) different filters \(\mtrx{W}_r\in\symbb{R}^{d'\times d}\) are used for capturing the arcs.
 With highly multi-relational data, the number of parameters grow rapidly since a full matrix needs to be estimated for all relations, even rare ones.
 To address this issue, \textcite{rgcn} propose to either constrain the matrices \(\mtrx{W}_r\) to be block-diagonal, or to decompose them on a small basis \(\tnsr{Z}^{(\ell)}\in\symbb{R}^{B\times d'\times d}\):
 \begin{equation*}
 	\mtrx{W}^{(\ell)}_r = \sum_{b=1}^{B} a_{rb}^{(\ell)} \mtrx{Z}_b^{(\ell)},
 \end{equation*}
 where \(B\) is the size of the basis and \(\vctr{a}_r\) are the parametric weights for the matrices \(\mtrx{W}_r\).
 
 \Textcite{rgcn} evaluate their model on two tasks.
 First, they evaluate on an entity classification task using a simple softmax layer with a cross-entropy loss on top of the vertex representation at the last layer (\(\mtrx{H}^{(L)}\) as defined by Equation~\ref{eq:graph:r-gcn layer}).
 Second, more closely related to relation extraction, they evaluate on a relation prediction task.
 \begin{marginparagraph}
 	This is similar to the evaluation of TransE reported in Section~\ref{sec:context:transe}; except that instead of predicting a missing entity in a tuple \((e_1, r, e_2)\in\kbSet\), the model must predict the missing relation, assuming \hypothesis{1-adjacency} in the process.
 \end{marginparagraph}
 Given a pair of entity \((e_1, e_2)\in\entitySet^2\), the model must predict the relation \(r\in\relationSet\) between them, such that \((e_1, r, e_2)\in\kbSet\).
 To this end, \textcite{rgcn} employ the DistMult model which can be seen as a \textsc{rescal} model (Section~\ref{sec:context:rescal}) where the interaction matrices are diagonal.
 The energy of a fact is defined as:
 \begin{equation*}
 	\psi_\text{DistMult}(e_1, r, e_2) = \vctr{u}_{e_1}\transpose \mtrx{C}_r \vctr{u}_{e_2},
 \end{equation*}
 where \(\vctr{u}_e\) is the embedding of the entity at the last layer of the \textsc{r-gcn}: \(\vctr{u}_e=\vctr{h}^{(L)}_e\) and \(\mtrx{C}_r\in\diagonal(\symbb{R}^d)\) is a diagonal matrix parameter.
 The probability associated to a fact by DistMult is proportional to the exponential of the energy function \(\psi_\text{DistMult}\).
 Therefore, a missing relation between \(e_1, e_2\in\entitySet\) can be predicted by taking the softmax over relations \(r\in\relationSet\) of \(\psi_\text{DistMult}(e_1, r, e_2)\).
 \textsc{r-gcn}s are trained using negative sampling (Section~\ref{sec:context:negative sampling}) on the entity classification and relation prediction tasks.
 This is similar to the training of TransE, where the main difference is that the entity embeddings are computed using \textsc{r-gcn} layers instead of being directly fetched from an entity embedding matrix.
 
 A limitation of \textsc{r-gcn}s is that they only rely on vertices' representation.
 Even when the evaluation involves the classification of arcs (as is the case with relation prediction), this is only done by combining the representations of the endpoints (using DistMult).
 
 Several works build upon \textsc{r-gcn}.
 \textsc{gp-gnn} \parencitex{gp-gnn} applies a similar model to the supervised relation extraction task.
 In this case, the graph is attributed with sentences instead of relations; therefore, the weight matrices \(\mtrx{W}_r\) are generated from the sentences instead of using an index of all possible relations.
 They apply their model to Wikipedia distantly supervised by Wikidata.
 However, the classification is still made from the representation of the endpoints of arcs.
 Related work also appears in the \emph{heterogeneous graph} community \parencitex{heterogeneous_attention, heterogeneous_transformer}.
 Heterogeneous graphs are graphs with labels on both vertices and arcs.
 The model proposed by \textcite{heterogeneous_transformer} is similar to \textsc{r-gcn} with an attention mechanism more akin to the transformer's attention (Section~\ref{sec:context:transformer attention}) than classical attention (Section~\ref{sec:context:attention}).
 The canonical evaluation datasets of this community are citation graphs.
 Vertices are assigned labels such as ``people,'' ``article'' and ``conference,'' while arcs are labeled with a small number of domain-specific relations: \textsl{author}, \textsl{published at}, \textsl{cite}, etc.
 The evaluation task typically corresponds to entity prediction.
 
 \subsection{Weisfeiler--Leman Isomorphism Test}
 \label{sec:graph:weisfeiler-leman}
 \begin{marginfigure}[-18mm]
 	\centering
 	\input{mainmatter/graph/isomorphism.tex}
 	\scaption[Example of isomorphic graphs.]{
 		Example of isomorphic graphs.
 		Each vertex \(i\) in the first graph corresponds to the \(i\)-th letter of the alphabet in the second graph.
 		Alternatively, these graphs have nontrivial automorphism, for example, by mapping vertex \(i\) to vertex \(9-i\).
 		\label{fig:graph:isomorphism}
 	}
 \end{marginfigure}
 
 In this section, we introduce the theoretical background of \textsc{gcn}s.
 This is of particular interest to us since this theoretical background is more closely related to unsupervised relation extraction than \textsc{gcn}s can be at first glance.
 As stated in the introduction to the thesis, relations emerge from repetitions.
 In particular, we expect that two identical (sub-)graphs convey the same relations.
 However, testing whether two graphs are identical is a complex problem.
 Indeed, we have to match each of the \(n\) vertices of the first graph to one of the \(n\) possibilities in the second graph.
 Naively, we need to try all \(n!\) possibilities.
 This is known as the graph isomorphism problem.
 Two simple graphs \(G_1 = (V_1, E_1)\), \(G_2 = (V_2, E_2)\) are said to be isomorphic (\(G_1\simeq G_2\)) iff there exists a bijection \(f\colon V_1\to V_2\) such that \((u, v)\in E_1 \iff (f(u), f(v))\in E_2\).
 Figure~\ref{fig:graph:isomorphism} gives an example of two isomorphic graphs.
 
 The various \textsc{gcn} methods introduced thus far can be seen as generalizations of the Weisfeiler--Leman%
 \sidenote[][-1cm]{
 	Often spelled Weisfeiler--Lehman, \textcite{leman_spelling} indicates that Andreĭ Leman preferred to transliterate his name without an ``h.''
 }
 isomorphism test \parencitex{weisfeiler-leman}, which tests whether two graphs are isomorphic.
 The \(k\)-dimensional Weisfeiler--Leman isomorphism test (\(k\)-dim \textsc{wl}) is a polynomial-time algorithm assigning a color to each \(k\)-tuple of vertices%
 \sidenote{An ordered sequence of \(k\) vertices, that is an element of \(V^k\), not necessarily connected.}
 such that two isomorphic graphs have the same coloring.
 With a bit of work, the general \(k\)-dim \textsc{wl} algorithm can be implemented in \(O(k^2 n^{k+1}\log n)\) \parencite{weisfeiler-leman_complexity}.
 However, there exist pairs of graphs that are not isomorphic, yet are assigned with the same coloring by the Weisfeiler--Leman test \parencitex{weisfeiler-leman_fail}[-2.5mm].
 At the time of writing, the precise membership of the graph isomorphism problem with respect to the polynomial complexity classes is still conjectural.
 No polynomial-time algorithm nor reduction from \textsc{np}-complete problems are known.
 This makes graph isomorphism one of the prime candidates for the \textsc{np}-intermediate complexity class.%
 \sidenote{
 	The class of \textsc{np} problems neither in \textsc{p} nor \textsc{np}-complete.
 	It is guaranteed to be non-empty if \(\textsc{p}\neq\textsc{np}\).
 	Clues for the \textsc{np}-intermediateness of the graph isomorphism problem can be found in the fact that the counting problem is in \textsc{np} \parencite{gi_counting} and more recently, from the fact that a quasi-polynomial algorithm exists \parencite{gi_quasipoly}.
 }
 
 \begin{algorithm}
 	\centering
 	\begin{minipage}[b]{8cm}
 		\input{mainmatter/graph/Weisfeiler-Leman.tex}
 	\end{minipage}
 	\scaption[The Weisfeiler--Leman isomorphism test.]{
 		The Weisfeiler--Leman isomorphism test.
 		The double braces \(\lMultiBrace\ \rMultiBrace\) denote a multiset.
 		Since \(\symfrak{I}_\ell\) is indexed with the previous coloring \(\chi_{\ell-1}(\vctr{x})\) of the vertices---alongside \(c_\ell(x)\)---the number of color classes is strictly increasing until the last iteration when it remains constant.
 		Since the last coloring is stable, we refer to it as \(\chi_\infty\).
 		\label{alg:graph:weisfeiler-leman}
 	}
 \end{algorithm}
 
 The general \(k\)-dim \textsc{wl} test is detailed in Algorithm~\ref{alg:graph:weisfeiler-leman}.
 It is a refinement algorithm, which means that at a given iteration, color classes can be split, but two \(k\)-tuples with different colors at iteration \(\ell\) can't have the same color at iteration \(\ell'>\ell\).
 Initially, all \(k\)-tuples \(x\) are assigned a color according to their isomorphism class \(\operatorname{iso}(x)\).
 We define the isomorphism class through an equivalence relation.
 For two \(k\)-tuples \(\vctr{x}, \vctr{y}\in V^k\), \(\operatorname{iso}(x)=\operatorname{iso}(y)\) iff:%
 \sidenote{
 	To avoid having to align two colorings, the \textsc{wl} algorithm is usually run on the disjoint union of the two graphs.
 	So, strictly speaking, it tests for automorphism (isomorphic endomorphism).
 	Therefore we can assume \(\vctr{x}\) and \(\vctr{y}\) are from the same vertex set \(V\).
 }
 \begin{itemize}
 	\item \(\forall i, j \in [1, \dotsc, k]: x_i=x_j \iff y_i=y_j\)
 	\item \(\forall i, j \in [1, \dotsc, k]: (x_i, x_j)\in E \iff (y_i, y_j)\in E\)
 \end{itemize}
 Intuitively, this checks whether \(x_i \mapsto y_i\) is an isomorphism for the subgraphs built from the \(k\) vertices \(\vctr{x}\) and \(\vctr{y}\).
 This is not the same as the graph isomorphism problem since here, the candidate isomorphism is given, we don't have to test the \(k!\) possibilities.
 
 The coloring of \(\vctr{x}\in V^k\) is refined at each step by juxtaposing it with the coloring of its neighbors \(\gfneighbors^k(\vctr{x})\).
 We need to reindex the new colors at each step since the length of the color strings would grow exponentially otherwise.
 The set of neighbors%
 \sidenote{
 	Note that the kind of neighborhood defined by \(\gfneighbors^k\) completely disregards the edges in the graph.
 	For this reason, it is sometimes called the \emph{global neighborhood}.
 }
 of a \(k\)-tuple for \(k\geq 2\) is defined as:
 \begin{equation*}
 	\gfneighbors^k(\vctr{x}) = \left\{\, \vctr{y}\in V^k \middlerel{|} \exists i\in[1,\dotsc,k]: \forall j\in[1,\dotsc,k]: j\neq i \implies x_j=y_j \,\right\}.
 \end{equation*}
 In other words, the \(k\)-tuples \(\vctr{y}\) neighboring \(\vctr{x}\) are those differing by at most one vertex with \(\vctr{x}\).
 
 The 1-dim \textsc{wl} test is also called the \emph{color refinement} algorithm.
 In this case, \(\gfneighbors^1(x)\) is simply \(\gfneighbors(x)\) the set of neighbors of \(x\).
 The isomorphism class of a single vertex is always the same, so \(\chi_0\) assigns the same color to all vertices.
 The first iteration of the algorithm groups vertices according to their degree (the multiplicity of the sole element in the multiset \(c_1(x)\)).
 The second iteration \(\chi_2\) then colors each vertex according to its degree \(\chi_1\) and the degree of its neighbors \(c_2\).
 And so on and so forth until \(\chi\) does not change anymore.
 
 The \textsc{gcn} introduced in the previous sections can be seen as variants of the 1-dim \textsc{wl} algorithm where the index \(\symfrak{I}_\ell\) is replaced with a neural network such as \(\operatorname{aggregate}^{(\ell)}_\text{mean}\) given in Section~\ref{sec:graph:spatial gcn}.
 In this case \(\chi_\ell\) corresponds to \(\mtrx{H}^{(\ell)}\) the activations at layer \(\ell\).